package com.liunian.algorithmstudy.str;

public class StrStr28 {

	public int strStr(String haystack, String needle) {
		int n = needle.length();
		char[] needleChars = needle.toCharArray();
		int[] next = getNext(needleChars, n);
		char[] haystackChars = haystack.toCharArray();
		int j = 0;
		for (int i = 0; i < haystackChars.length; i++) {
			while (j > 0 && haystackChars[i] != needleChars[j]) {
				j = next[j - 1];
			}
			if (haystackChars[i] == needleChars[j]) {
				j++;
			}
			if (j == n) {
				return i - j + 1;
			}
		}
		return -1;
	}

	private int[] getNext(char[] chars, int n) {
		int[] next = new int[n];
		int j = 0;
		next[0] = 0;
		for (int i = 1; i < n; i++) {
			while (j > 0 && chars[i] != chars[j]) {
				j = next[j - 1];
			}
			if (chars[i] == chars[j]) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}

	public static void main(String[] args) {
		StrStr28 str = new StrStr28();
		System.out.println(str.strStr("aasadbutsad", "sad"));
	}

}
